package chapter15;

import java.util.List;

/**
 * 动态规划-切钢条
 */
public class CutRob {

    /**
     * 自顶向下递归,时间复杂度2^n
     * <p>
     * p:钢条的方案,数据下标代表长度,数值代表金额
     * n:需要的长度
     * 钢条越长则金额越高
     * <p>
     * 最优子结构：
     * max p[n-1]+p[n-2]+p[n-3]...p[0]
     */
    public static int cutRob(int[] p, int n) {
        if (n == 0) {
            return 0;
        }
        int q = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            q = Math.max(q, p[i] + cutRob(p, n - i));
        }
        return q;
    }

    /**
     * 备忘录的自顶向下,时间复杂度n^2
     * <p>
     * 备忘录:
     * 分析递归树,设n=4
     * *
     * *            4
     * *        /   |   \
     * *       1    2    3
     * *            |   /   \
     * *            1  2     1
     * *               |
     * *               1
     * *
     * 可以看到1和2都重复计算,代表从高到底的过程中,会有大量被重复递归计算的逻辑,
     * 为了消除重复的递归逻辑,我们将已计算的值都缓存起来,这里用的就是数组r,代表当前数组小标大小的钢条最优的多少钱金额,如果r[n]>0代表计算过,直接从缓存r中获得
     */
    public static int memoizedCutRob(int[] p, int n) {
        int[] r = new int[n + 1];
        return memoizedCutRobAux(p, n, r);
    }

    public static int memoizedCutRobAux(int[] p, int n, int[] r) {
        // 从备忘录中取
        int m = r[n];
        if (m > 0) {
            return m;
        }
        int q = Integer.MIN_VALUE;
        if (n == 0) {
            q = 0;
        }
        for (int i = 1; i <= n; i++) {
            q = Math.max(q, p[i] + memoizedCutRobAux(p, n - i, r));
        }
        r[n] = q;
        return q;
    }

    /**
     * 自底向上循环结构,n^2
     * <p>
     * 与自顶向下相比,问题是结构可以看作从递归树的叶子结点出发,向上求解,优点是不会像递归那样造成的大量空间占用
     */
    public static int bottomUpCutRob(int[] p, int n) {
        int[] r = new int[n + 1];
        for (int j = 1; j <= n; j++) {
            int q = Integer.MIN_VALUE;
            for (int i = 1; i <= j; i++) {
                q = Math.max(q, p[i] + r[j - i]);
            }
            r[j] = q;
        }
        return r[n];
    }

    public static List<int[]> extendedBottomUpCutRob(int[] p, int n) {
        int[] r = new int[n + 1];
        int[] s = new int[n + 1];
        for (int j = 1; j <= n; j++) {
            int q = Integer.MIN_VALUE;
            for (int i = 1; i <= j; i++) {
                if (q < p[i] + r[j - i]) {
                    q = p[i] + r[j - i];
                    s[j] = i;
                }
            }
            r[j] = q;
        }
        return List.of(r, s);
    }

    public static int cutRobAndCost(int[] p, int n, int cost) {
        if (n == 0) {
            return 0;
        }
        int q = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            q = Math.max(q, p[i] + cutRobAndCost(p, n - i, cost) - cost);
        }
        return q;
    }

    public static List<int[]> extendedBottomUpCutRobAndCost(int[] p, int n, int cost) {
        int[] r = new int[n + 1];
        int[] s = new int[n + 1];
        for (int j = 1; j <= n; j++) {
            int q = Integer.MIN_VALUE;
            for (int i = 1; i <= j; i++) {
                int profit = p[i] + r[j - i] - cost;
                if (q < profit) {
                    q = profit;
                    s[j] = i;
                }
            }
            r[j] = q;
        }
        return List.of(r, s);
    }

    public static void printCutRobSolution(int[] p, int n) {
        List<int[]> res = extendedBottomUpCutRob(p, n);
        System.out.println("p->" + res.get(0)[n]);
        int n1 = n;
        while (n1 > 0) {
            System.out.println("s->" + res.get(1)[n1]);
            n1 = n1 - res.get(1)[n1];
        }
    }

    public static void printCutRobSolutionAndCost(int[] p, int n, int cost) {
        List<int[]> res = extendedBottomUpCutRobAndCost(p, n, cost);
        System.out.println("pc->" + res.get(0)[n]);
        int n1 = n;
        while (n1 > 0) {
            System.out.println("sc->" + res.get(1)[n1]);
            n1 = n1 - res.get(1)[n1];
        }
    }

    public static void printMemoizedCutRobSolution(int[] p, int n) {
        List<int[]> res = memoizedCutRobSolution(p, n);
        System.out.println("mc->" + res.get(0)[n]);
        int n1 = n;
        while (n1 > 0) {
            System.out.println("mc->" + res.get(1)[n1]);
            n1 = n1 - res.get(1)[n1];
        }
    }

    public static List<int[]> memoizedCutRobSolution(int[] p, int n) {
        int[] r = new int[n + 1];
        int[] s = new int[n + 1];
        memoizedCutRobAuxSolution(p, n, r, s);
        return List.of(r, s);
    }

    public static int memoizedCutRobAuxSolution(int[] p, int n, int[] r, int[] s) {
        int m = r[n];
        if (m > 0) {
            return m;
        }
        int q = Integer.MIN_VALUE;
        if (n == 0) {
            q = 0;
        }
        for (int i = 1; i <= n; i++) {
            int profit = p[i] + memoizedCutRobAuxSolution(p, n - i, r, s);
            if (q < profit) {
                q = profit;
                s[n] = i;
            }
        }
        r[n] = q;
        return q;
    }

}
